package com.fengdi.book.middle;

import com.fengdi.publicObject.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class TreeAndGraph {
    public static class InorderTraversal {
        public List<Integer> list = new ArrayList<>();

        public List<Integer> inorderTraversal(TreeNode root) {
            if(root == null) return new ArrayList<>();
            inorder(root);
            return list;
        }

        private void inorder(TreeNode root) {
            if (root == null) return;
            inorder(root.left);
            list.add(root.val);
            inorder(root.right);
        }
    }

    public static class ZigzagLevelOrder {
        public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
            if(root==null) return new ArrayList<>();

            List<List<Integer>> result = new ArrayList<>();
            List<TreeNode> queue = new ArrayList<>();
            int depth = 1;
            queue.add(root);

            while(!queue.isEmpty()) {
                int level = queue.size();
                List<Integer> list = new ArrayList<>();
                for(int i = 0; i < level; i++) {
                    if(depth % 2 != 0) {
                        TreeNode node = queue.removeFirst();
                        list.add(node.val);
                        if(node.left != null) queue.add(node.left);
                        if(node.right != null) queue.add(node.right);
                    }else {
                        TreeNode node = queue.removeLast();
                        list.add(node.val);
                        if(node.right != null) queue.addFirst(node.right);
                        if(node.left != null) queue.addFirst(node.left);
                    }
                }
                result.add(list);
                depth++;
            }

            return result;
        }
    }

    public static class BuildTree {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            List<Integer> preorderList = new ArrayList<>();
            List<Integer> inorderList = new ArrayList<>();
            for(int i = 0; i < preorder.length; i++) {
                preorderList.add(preorder[i]);
                inorderList.add(inorder[i]);
            }
            return buildTreeHelper(preorderList, inorderList);
        }

        private TreeNode buildTreeHelper(List<Integer> preorderList, List<Integer> inorderList) {
            if(inorderList.isEmpty()) return null;

            int rootVal = preorderList.removeFirst();
            TreeNode root = new TreeNode(rootVal);
            int midIndex = inorderList.indexOf(rootVal);
            root.left = buildTreeHelper(preorderList, inorderList.subList(0, midIndex));
            root.right = buildTreeHelper(preorderList, inorderList.subList(midIndex + 1, inorderList.size()));
            return root;
        }
    }

    public static class Connect {
        public class Node extends TreeNode {
            public Node next;
            public Node(int val) {
                super(val);
            }
        }

        public Node connect(Node root) {
            List<Node> queue = new ArrayList<>();
            if(root == null) return null;

            queue.add(root);
            while(!queue.isEmpty()) {
                int level = queue.size();
                for(int i = 0; i < level; i++) {
                    Node node = queue.removeFirst();
                    node.next = i + 1 < level ? queue.getFirst() : null;

                    if(node.left != null) queue.add((Node) node.left);
                    if(node.right != null) queue.add((Node) node.right);
                }
            }
            return root;
        }
    }

    public static class KthSmallest {
        public int kthSmallest(TreeNode root, int k) {
            List<Integer> list = new ArrayList<>();
            inorder(root, list);
            return list.get(k - 1);
        }

        private void inorder(TreeNode root, List<Integer> list) {
            if(root == null) return;
            inorder(root.left, list);
            list.add(root.val);
            inorder(root.right, list);
        }
    }

    public static class NumIslands {
        private int count = 0;
        public int numIslands(char[][] grid) {
            if(grid.length == 0 || grid[0].length == 0) return 0;

            for(int i = 0; i < grid.length; i++) {
                for(int j = 0; j < grid[0].length; j++) {
                    if(grid[i][j] == '1') {
                        this.count++;
                        dfs(grid, i, j);
                    }
                }
            }

            return this.count;
        }

        private void dfs(char[][] grid, int i, int j) {
            if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;

            grid[i][j] = '0';
            dfs(grid, i + 1, j);
            dfs(grid, i - 1, j);
            dfs(grid, i, j + 1);
            dfs(grid, i, j - 1);
        }
    }
}
